#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node_s {
	long data;
	struct node_s *left;
	struct node_s *right;
	int max_left;
	int max_right;
} node_t;

void insert_tree(node_t **root, long data)
{
	node_t *new, *p;

	new = (node_t *)malloc(sizeof(node_t));
	if (new == NULL) {
		printf("malloc for node failed\n");
		return;
	}
	memset(new, 0, sizeof(node_t));
	new->data = data;

	if (NULL == *root) {
		*root = new;
		return;
	}

	p = *root; 
	while(1) {
		if (data >= p->data) {
			if (p->right)
				p = p->right;
			else {
				p->right = new;
				break;
			}
		} else {
			if (p->left)
				p = p->left;
			else {
				p->left = new;
				break;
			}
		}
	}
}

void create_tree(node_t **root, int n)
{
	long ran_a, ran_b, data;
	int i;

	for (i = 0; i < n; i ++) {
		ran_a = random();
		ran_b = random();
		data = ran_a + (ran_a - ran_b) + ((ran_a + ran_b) >> 1);
		data %= 100;
		printf("%d times:insert:%ld\n", i, data);
		insert_tree(root, data);
	}
}

void pre_scan_tree(node_t *node)
{
	printf("%ld\t", node->data);
	if (node->left)
		pre_scan_tree(node->left);
	if(node->right)
		pre_scan_tree(node->right);
}

void mid_scan_tree(node_t *node)
{
	if (node->left)
		mid_scan_tree(node->left);
	printf("%ld\t", node->data);
	if(node->right)
		mid_scan_tree(node->right);
}

int max_len = 0;
void max_distance(node_t *node)
{
	int tmp = 0;
	if (!node)
		return;
	
	if (node->left) {
		max_distance(node->left);
		if (node->left->max_left > node->left->max_right)
			node->max_left = node->left->max_left + 1;
		else 
			node->max_left = node->left->max_right + 1;
	} else 
		node->max_left = 0;
	if (node->right) {
		max_distance(node->right);
		if (node->right->max_left > node->right->max_right)
			node->max_right = node->right->max_left + 1;
		else 
			node->max_right = node->right->max_right + 1;
	} else 
		node->max_right = 0;

	tmp = node->max_left + node->max_right;
	if (tmp > max_len)
		max_len = tmp;
}

int main()
{
	int n = 15;
	node_t *root = NULL;

	create_tree(&root, n);
	printf("\n");
	pre_scan_tree(root);
	printf("\n");
	mid_scan_tree(root);
	max_distance(root);
	printf("\nmad_len:%d\n", max_len);
	return 0;
}

